package com.hc.programming.tree;

import java.util.AbstractList;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
 * 叶子节点 是指没有子节点的节点。
 * <p>
 * 示例 1：
 * <a href="./二叉树的所有路径-示例1.png">示例1</a>
 * 输入：root = [1,2,3,null,5]
 * 输出：["1->2->5","1->3"]
 * 示例 2：
 * 输入：root = [1]
 * 输出：["1"]
 * <p>
 * 提示：
 * 树中节点的数目在范围 [1, 100] 内
 * -100 <= Node.val <= 100
 *
 * @author huangchao E-mail:fengquan8866@163.com
 * @version 创建时间：2024/10/14 21:26
 */
public class 二叉树的所有路径 {
    public static void main(String[] args) {
        Integer[] arr = new Integer[]{1, 2, 3, null, 5};
        TreeNode tree = TreeNode.tree(arr);
        System.out.println(Arrays.toString(arr) + "=2,--" + binaryTreePaths(tree));
        arr = new Integer[]{1};
        tree = TreeNode.tree(arr);
        System.out.println(Arrays.toString(arr) + "=1,--" + binaryTreePaths(tree));
    }

    public static List<String> binaryTreePaths(TreeNode root) {
//        List<String> list = new ArrayList<>();
//        binaryTreePaths(root, new StringBuilder(), list);
//        return list;

        return new AbstractList<String>() {
            final List<String> list = new ArrayList<>();
            final StringBuilder stringBuilder = new StringBuilder();

            @Override
            public String get(int index) {
                init();
                return list.get(index);
            }

            @Override
            public int size() {
                init();
                return list.size();
            }

            void init() {
                if (!list.isEmpty()) return;
                binaryTreePaths(root, stringBuilder, list);
            }
        };
    }

    private static void binaryTreePaths(TreeNode root, StringBuilder stringBuilder, List<String> list) {
        if (root == null) return;
        int length = stringBuilder.length();
        stringBuilder.append(root.val);
        if (root.left == null && root.right == null) {
            list.add(stringBuilder.toString());
        } else {
            stringBuilder.append("->");
            if (root.left != null) binaryTreePaths(root.left, stringBuilder, list);
            if (root.right != null) binaryTreePaths(root.right, stringBuilder, list);
        }
        stringBuilder.setLength(length);
    }

}
